package main

/* 贪心及其数学证明

首先，两个交换的比特必须是不同的，否则交换无影响。

不失一般性，假设 $x$ 参与交换的比特为 $0$，$y$ 参与交换的比特为 $1$，交换的位置为第 $k$ 位。

记 $y=y'+2^k$，则交换前两数的乘积为

$$
x\cdot y = x\cdot (y'+2^k) = x\cdot y'+x\cdot 2^k
$$

交换后两数的乘积为

$$
(x+2^k)\cdot (y-2^k) = (x+2^k)\cdot y' = x\cdot y'+y'\cdot 2^k
$$

对比两个不等式可知，要使交换后乘积变小，需要满足

$$
x>y'
$$

这一不等式表明，对于一个数 $y$，如果我们不断地将其比特为 $1$ 的位置与另一个满足该不等式的数交换，就可以将乘积不断减小。由于题目要求计算最小非零乘积，我们可以先将 $y$ 减小至 $0$，然后再寻找一个最低位为 $1$ 的数进行交换，从而让 $y$ 变成 $1$。

由于 $\textit{nums}$ 包含了 $[1, 2^p - 1]$ 内的所有整数，我们可以将其分为两组，小于 $2^{p-1}$ 的为一组，记作 $A$，其余的为另一组，记作 $B$。则 $B$ 组中除了 $2^p-1$ 之外，其余的数均可以和 $A$ 组中的数一一配对，要求这两个数之和为 $2^p-1$。每对配对的数就可以按照上述交换流程交换，交换后的结果为 $1$ 和 $2^p-2$。

交换后，每一对的乘积为 $2^p-2$，这一共有 $2^{p-1}-1$ 对，再算上不参与配对的 $2^p-1$，得到最小乘积为

$$
(2^p-1)\cdot (2^p-2)^{2^{p-1}-1}
$$

由于幂次很大，计算时需要用到快速幂。不了解的读者可以参考 [50. Pow(x, n)](https://leetcode-cn.com/problems/powx-n/)。

*/

// github.com/EndlessCheng/codeforces-go
const mod int = 1e9 + 7

func minNonZeroProduct(p int) int {
	return (1<<p - 1) % mod * pow(1<<p-2, 1<<(p-1)-1) % mod
}

func pow(x, n int) int {
	res := 1
	for x %= mod; n > 0; n >>= 1 {
		if n&1 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}
